package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordSearch {

	public static void main(String[] args) {
		WordSearch object = new WordSearch();
		char[][] board = {{'b'},{'a'},{'b'}};
		String word = "bbabab";
		object.exist(board, word);
	}
	
	public boolean exist(char[][] board, String word) {
		if (board == null) {
			return word == null;
		}
		char[] words = word.toCharArray();
		for (int x = 0; x < board.length; x++) {
			for (int y = 0; y < board[0].length; y++) {
				if (exist(board, x, y, words, 0)) {
					return true;
				}
			}
		}
		return false;
	}

	private boolean exist(char[][] board, int x, int y, char[] word, int i) {
		if (i == word.length)
			return true;
		if (x < 0 || y < 0 || x == board.length || y == board[x].length)
			return false;
		if (board[x][y] != word[i])
			return false;
		// 这里为了节约空间，使用了这种方式来进行标记该位置是否已经访问过
		board[x][y] ^= 256;
		boolean exist = exist(board, x, y + 1, word, i + 1)
				|| exist(board, x, y - 1, word, i + 1)
				|| exist(board, x + 1, y, word, i + 1)
				|| exist(board, x - 1, y, word, i + 1);
		// 进行还原
		board[x][y] ^= 256;
		return exist;
	}
	
}
